﻿#include "Astart.h"
#include <algorithm>

namespace CPP35{


	bool Astart::findPath(Vec2 start, Vec2 end, vector<Vec2>& path)
	{
		bool result = false;					//是否找到了终点
		this->end = end;						//终点坐标
		Node*endNode=nullptr;					//终点路径
		closeList.push_back(new Node(start.x, start.y, 0, getH(start)));
		int length = 0;
		while (length < closeList.size()&&!endNode){
			length = closeList.size();
			addRound(closeList.back());

			Node* minF = nullptr;     //存储最小的值
			int minIndex=0;				//最小值的下标
			for (int i = 0; i < openList.size(); i++)
			{
				Node *n = openList[i];
				if (n->x==end.x&&n->y==end.y)    //判断是否找到终点
				{
					endNode = n;
					result = true;
					break;
				}
				if (!minF||minF->getF()>n->getF())	//找到最小的F值
				{
					minF = n;
					minIndex = i;
				}
			}
			if (minF)
			{
				openList.erase(openList.begin() + minIndex);
				closeList.push_back(minF);
			}
		}

		//是否找到了终点
		if (result)
		{
			vector<Vec2> tmp;
			while (endNode)
			{
				tmp.push_back(Vec2(endNode->x, endNode->y));
				endNode = endNode->parent;
			}
			//反向遍历路径
			path.assign(tmp.rbegin(), tmp.rend());
		}
		destory();
		return result;
	}

	void Astart::addRound(Node* n)
	{
		static vector<Vec2> dir = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
		for (auto v2 : dir)
		{
			v2.x += n->x;
			v2.y += n->y;
			if (filer(v2))
			{
				openList.push_back(new Node(v2.x, v2.y, n->G + 1, getH(v2), n));
			}
		}
	}

	bool Astart::filer(Vec2 v2)
	{
		return !(isVisited(openList, v2)
				|| isVisited(closeList, v2)
				|| !outFiler(v2));
				
	}

	bool Astart::isVisited(vector<Node*>& ls, Vec2 v2)
	{
		for (auto& n : ls)
			if (n->x == v2.x&&n->y == v2.y)
				return true;
		return false;
	}

	void Astart::destory()
	{
		for (Node *n : openList)
		{
			delete n;
		}
		for (Node *n : closeList)
		{
			delete n;
		}
	}

	int Astart::getH(Vec2 now)
	{
		return std::abs(end.x - now.x) + std::abs(end.y - now.y);
	}
}
